import java.util.Stack;

public class Board {
	private final int N;
	private final int[][] board;
	
    public Board(int[][] blocks) {           // construct a board from an N-by-N array of blocks
    	N = blocks.length;
    	this.board = new int[N][N];
    	
    	for (int i = 0; i < N; i++)
    		for (int j = 0; j < N; j++)
    			board[i][j] = blocks[i][j]; 	// (where blocks[i][j] = block in row i, column j)
    }
                                          
    public int dimension() {                 // board dimension N
    	return N;
    }
    
    public int hamming() {                   // number of blocks out of place
    	int sum = 0;
    	for (int i = 0; i < N; i++)
    		for (int j = 0; j < N; j++) {
    			if (board[i][j] == 0)
    				continue;
    			
    			if (board[i][j] != (i*N+j+1))
    				sum++;
    		}
    	
    	return sum;
    }
    public int manhattan() {                 // sum of Manhattan distances between blocks and goal
    	int sum = 0;
    	for (int i = 0; i < N; i++)
    		for (int j = 0; j < N; j++) {
    			int x = board[i][j];
    			if (x == 0)
    				continue;
    			
    			sum += Math.abs((int) Math.ceil((double) x/N - 1) - i) + Math.abs((x-1) % N - j);
    		}
    	
    	return sum;
    }

    
    public boolean isGoal() {                // is this board the goal board?
    	return (hamming() == 0);
    }
    
    public Board twin() {                    // a board obtained by exchanging two adjacent blocks in the same row
    	int[][] twin = new int[N][N];
    	
    	for (int i = 0; i < N; i++)
    		for (int j = 0; j < N; j++)
    			twin[i][j] = board[i][j];
    	
    	outerLoop: for (int i = 0; i < N; i++)
    		for (int j = 1; j < N; j++)
    			if (twin[i][j] != 0 && twin[i][j-1] != 0) {
    				int temp = twin[i][j];
    				twin[i][j] = twin[i][j-1];
    				twin[i][j-1] = temp;
    				break outerLoop;
    			}
    	
    				
    	return new Board(twin);
    }
    
    public boolean equals(Object y) {        // does this board equal y?
    	if (this == y) return true;
    	
    	if (y == null) return false;
    	
    	if (this.getClass() != y.getClass())
    		return false;
    	
    	if (dimension() != ((Board) y).dimension())
    		return false;
    	
    	for (int i = 0; i < N; i++)
    		for (int j = 0; j < N; j++) {
    			if (board[i][j] != ((Board) y).board[i][j])
    				return false;
    		}
    	
    	return true;
    	
    }
    
    public Iterable<Board> neighbors() {    // all neighboring boards
    	Stack<Board> boards = new Stack<Board>();
    	
    	int[][] newBoard = new int[N][N];
    	
    	int i0 = 0, j0 = 0;
    	
    	for (int i = 0; i < N; i++)
    		for (int j = 0; j < N; j++) {
    			newBoard[i][j] = board[i][j];
    			if (board[i][j] == 0) {
    				i0 = i;
    				j0 = j;
    			}
    				
    		}
    	
    	for (int j = -1; j < 2; j += 2) {
			int newj = j0 + j;
	
			if (newj == N || newj < 0)
				continue;
			
			int temp = newBoard[i0][j0];
			newBoard[i0][j0] = newBoard[i0][newj];
			newBoard[i0][newj] = temp;
			
			boards.push(new Board(newBoard));
			
			temp = newBoard[i0][j0];
			newBoard[i0][j0] = newBoard[i0][newj];
			newBoard[i0][newj] = temp;
		}
    	
    	for (int i = -1; i < 2; i += 2) {
			int newi = i0 + i;
	
			if (newi == N || newi < 0)
				continue;
			
			int temp = newBoard[i0][j0];
			newBoard[i0][j0] = newBoard[newi][j0];
			newBoard[newi][j0] = temp;
			
			boards.push(new Board(newBoard));
			
			temp = newBoard[i0][j0];
			newBoard[i0][j0] = newBoard[newi][j0];
			newBoard[newi][j0] = temp;
		}
    	
    	return boards;
    }
    
    public String toString() {               // string representation of the board (in the output format specified below)
    	String str = "";

    	str = str.concat(String.valueOf(N)).concat("\n");
    	
    	for (int i = 0; i < N; i++)
    		for (int j = 0; j < N; j++) {
    			if ((j+1) % N == 0)
    				str = str.concat(" " + board[i][j] + "\n");
    			else
    				str = str.concat(" " + board[i][j]);
    		}
    	
    	return str;
    }
 
	public static void main(String[] args) {
		
	}

}
